package eazy.DynamicProgramming;

public class maxSubArray_53 {
    public static void main(String[] args) {
    int[] a=new int[]{-2,1,-3,4,-1,2,1,-5,4};
        maxSubArray_53 maxSubArray_53 =new maxSubArray_53();
        System.out.println(maxSubArray_53.maxSubArray_Dynamic(a));
    }
    //最大连续子数组和
    public int maxSubArray_Dynamic(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            //x不停的动,如果pre+x有一直为整数,那么史高一直更新.
            //如果pre+x一直为负数,那么史高永远是当前的x.
            pre = Math.max(pre + x, x);
            //存史高
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}
